package _01_复杂度;

/*
    斐波那契数
    0 1 1 2 3 5 8 13
 */
public class Main {
    // O(n)
    public static int fib1(int n){
        if(n<=1) return n;
        int first = 0;
        int second = 1;

        // 只需要计算 n - 1 次 即可
        //   1+n-1+n-1+(n-1)*3 = n
        for(int i=0;i<n-1;++i){
            int sum = first + second;
            first = second;
            second = sum;
        }
        return second;
    }

    public static void main(String[] args) {
        Times.test("斐波那契测试",()->{
            System.out.println( fib1(64));
        });
    }
}
